# 135. 分发糖果
# n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
# 你需要按照以下要求，给这些孩子分发糖果：
# 每个孩子至少分配到 1 个糖果。
# 相邻两个孩子评分更高的孩子会获得更多的糖果。
# 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。


# 我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。
#
# 左规则：当 ratings[i−1]<ratings[i] 时，i 号学生的糖果数量将比 i−1 号孩子的糖果数量多。
# 右规则：当 ratings[i]>ratings[i+1] 时，i 号学生的糖果数量将比 i+1 号孩子的糖果数量多。
#
# 我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。
def candy(ratings):
    """
    :type ratings: List[int]
    :rtype: int
    """
    ratings_length = len(ratings)
    # 存放满足左规则的最小值
    left_rule = [0] * ratings_length
    for i in range(ratings_length):
        if i == 0 or ratings[i] <= ratings[i - 1]:
            left_rule[i] = 1
        else:
            left_rule[i] = left_rule[i - 1] + 1

    # 存放满足右规则的最小值
    right_rule = [0] * ratings_length
    for i in range(ratings_length - 1, -1, -1):
        if i == ratings_length - 1 or ratings[i] <= ratings[i + 1]:
            right_rule[i] = 1
        else:
            right_rule[i] = right_rule[i + 1] + 1

    result = 0
    for index in range(ratings_length):
        result += max(left_rule[index], right_rule[index])

    print(f"ratings:{ratings} , left_rule:{left_rule} , right_rule:{right_rule}")

    return result


ratings_1 = [1, 0, 2]
result = candy(ratings_1)
print(f"result:{result}")

ratings_2 = [1, 2, 2]
result = candy(ratings_2)
print(f"result:{result}")
